package com.justnow.offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;


public class Solution32_1 {
    /**
     * 广度优先遍历的方法，实现按层打印
     * @param root
     * @return
     */
    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }

        Queue<TreeNode> queue = new LinkedList<>(); //存放每个节点的内容
        ArrayList<Integer> array = new ArrayList<>(); //存放节点中的val内容

        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll(); //队头节点出队
            array.add(node.val);//队头节点中的数据存放到array中
            //依次往里面队列中插入队头节点的左右子节点
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
            //下次循环中先出的是队头的左子节点，然后将其保存到array中，接着其左子节点和右子节点分别插入到队列中
        };

        int size = array.size();
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = array.get(i);
        }

        return res;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}